package com.leetcode;

/**
 * 28. 实现 strStr()
 * KMP算法实现
 * https://leetcode-cn.com/problems/implement-strstr/solution/zhe-ke-neng-shi-quan-wang-zui-xi-de-kmp-8zl57/
 *
 * @author fy
 * @date 2022/4/7 14:28
 */
public class Solution28_1 {

    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }

        char[] haArr = haystack.toCharArray();
        char[] neArr = needle.toCharArray();

        int haLen = haArr.length;
        int neLen = neArr.length;

        return kmp(haArr, haLen, neArr, neLen);
    }

    private int kmp(char[] haArr, int haLen, char[] neArr, int neLen) {
        int[] next = next(neArr, neLen);
        int j = 0;
        for (int i = 0; i < haLen; i++) {
            // 发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
            // 前缀的后一位,和咱们移动模式串的含义相同
            while (j > 0 && haArr[i] != neArr[j]) {
                j = next[j - 1] + 1;
                // 超出长度时，可以直接返回不存在
                if (neLen - j + i > haLen) {
                    return -1;
                }
            }
            // 如果相同就将指针同时后移一下，比较下个字符
            if (haArr[i] == neArr[j]) {
                ++j;
            }
            // 遍历完整个模式串，返回模式串的起点下标
            if (j == neLen) {
                return i - neLen + 1;
            }
        }
        return -1;
    }

    // 返回kmp的next数组
    private int[] next(char[] arr, int len) {
        int[] next = new int[len];
        // 初始化next[0] 为-1
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < len; i++) {
            // 我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            // 因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            // 就要找 k+1前一个元素在next数组里的值,即next[k+1]
            while (k != -1 && arr[k + 1] != arr[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            // 然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (arr[k + 1] == arr[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }

    public static void main(String[] args) {
        String haystack = "mississippi";
        String needle = "issip";
        int res = new Solution28_1().strStr(haystack, needle);
        System.out.println(res);
    }

}
